/**
 * 给出一个字符串 s（仅含有小写英文字母和括号）。
 * 请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
 * 注意，您的结果中 不应 包含任何括号。
 * <p>
 * 示例 1：
 * 输入：s = "(abcd)"
 * 输出："dcba"
 * <p>
 * 示例 2：
 * 输入：s = "(u(love)i)"
 * 输出："iloveu"
 * 解释：先反转子字符串 "love" ，然后反转整个字符串。
 * <p>
 * 示例 3：
 * 输入：s = "(ed(et(oc))el)"
 * 输出："leetcode"
 * 解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。
 * <p>
 * 示例 4：
 * 输入：s = "a(bcdefghijkl(mno)p)q"
 * 输出："apmnolkjihgfedcbq"
 * <p>
 * 提示：
 * 0 <= s.length <= 2000
 * s 中只有小写英文字母和括号
 * 题目测试用例确保所有括号都是成对出现的
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01190m {

    public String reverseParentheses(String s) {
        if (s == null || s.length() <= 1) return s;
        char[] cs = s.toCharArray();
        for (int right = 0; right < cs.length; right++) {
            if (cs[right] == ')') { // 找到一个右括号
                int left = right - 1;
                while (cs[left] != '(') { // left指向与right配对的(
                    left--;
                }
                cs[right] = cs[left] = Character.MIN_VALUE; // 改为空字符
                reverse(cs, left, right);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char c : cs) {
            if (c != Character.MIN_VALUE) { // 不是空字符的，才是有效字符
                sb.append(c);
            }
        }
        return sb.toString();
    }

    /**
     * 翻转left+1到right-1的字符
     *
     * @param cs
     * @param left
     * @param right
     */
    private void reverse(char[] cs, int left, int right) {
        while (++left < --right) {
            char temp = cs[right];
            cs[right] = cs[left];
            cs[left] = temp;
        }
    }
}
